package LinkedList;

/*
 * 链表的插入操作
 * 分为带傀儡结点和不带傀儡结点
 * */
public class Operation_02 {

    public static void main(String[] args) {
        Node head = creatList();//创建不带傀儡结点的链表
        Node headDummy = creatListDummy();//创建带傀儡链表
        Node newNode = new Node(100);
//        Node node=delete(head,1);
//        print(node);
        Node node1=inset_1(head,newNode);
        print(node1);
        insetTail(head,newNode);
        print(head);
    }


    public static Node creatList() {
        Node a = new Node(1);
        Node b = new Node(1);
        Node c = new Node(1);
        Node d = new Node(4);
        Node e = new Node(1);

        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;
        e.next = null;

        return a;
    }

    //带傀儡的链表
    public static Node creatListDummy() {
        Node dummy = new Node(0);
        Node a = new Node(1);
        Node b = new Node(2);
        Node c = new Node(3);
        Node d = new Node(4);

        dummy.next = a;
        a.next = b;
        b.next = c;
        c.next = d;
        d.next = null;

        return dummy;
    }

    //打印链表
    public static void print(Node head) {
        Node cur = head;
        while (cur != null) {
            System.out.print(" " + cur.val);
            cur = cur.next;
        }
        System.out.println();
    }

    //打印带傀儡链表
    public static void printDummy(Node head) {
        Node cur = head.next;
        while (cur != null) {
            System.out.println(cur.val);
            cur = cur.next;
        }
    }

    //傀儡链表的头插
    public static void insertDummy(Node headDummy, Node newNode) {
        Node prev = headDummy;
        newNode.next = prev.next;
        prev.next = newNode;
        printDummy(headDummy);
    }


    //将新节点插入到1和2之间
    public static void inset1_2(Node head, Node newNode) {
        Node prev = head;
        newNode.next = prev.next;
        prev.next = newNode;
        print(head);
    }

    //将新节点的头插
    public static Node inset_1(Node head, Node newNode) {
        newNode.next = head;
        head = newNode;
//        print(head);
        return head;
    }

    //尾插一个节点
    public static void insetTail(Node head, Node newNode) {
        Node prev = head;
        while (prev != null && prev.next != null) {
            prev = prev.next;
        }
        prev.next = newNode;
        newNode.next = null;
        print(head);

    }

    //删除给定结点
    public static Node delete(Node head, Node toDelete) {
        Node prev = head;
        if (prev == toDelete) {
            prev = prev.next;
            return prev;
        }
        while (prev != null && prev.next != toDelete) {
            prev = prev.next;
        }
        if (prev == null) {
            System.out.println("没找到");
            return head;
        }
        prev.next = toDelete.next;
        print(head);
        return head;
    }


    //删除给定值
    public static Node delete(Node head, int val) {
        if(head==null){
            return null;
        }
        Node prev = head;
        while (prev.next != null) {
            if (prev.next.val == val) {
                prev.next = prev.next.next;
            }else{
                prev = prev.next;
            }

        }
        if(head.val==val){
            head=head.next;
        }
        return head;
    }

    public static int size(Node head) {
        int size = 0;
        for (Node cur = head; cur != null; cur = cur.next) {
            size++;
        }
        return size;
    }

    //给定下标删除
    public static Node delete2(Node head, int index) {
        int size = size(head);
        if (index < 0 || index >= size) {
            return null;
        }
        if (index == 0) {
            head = head.next;
            return head;
        }
        Node prev = head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        prev.next = prev.next.next;
        return head;
    }

}

